package calc;

import java.util.*;

public class Expression
{
    /* Static Inner Class */
    private static enum TYPE {
        DIGIT, OPERATOR;
    }

    private static class Token {
        public TYPE   type;
        public char   opt;
        public double num;

        public Token(char ch)  { type = TYPE.OPERATOR; opt = ch; }
        public Token(double n) { type = TYPE.DIGIT;    num = n;  }
    }

    /* Fields */
    private String       content;
    private Deque<Token> postfix;

    /* Constructors */
    public Expression()         { content = ""; postfix = new ArrayDeque<>(); }
    public Expression(String s) { content = s;  postfix = new ArrayDeque<>(); }

    /* Instance Methods */
    public void setContent(String s) { content = s; postfix.clear(); }

    public double getValue() {
        // 1. trim whitespace
        trim();

        // 2. check expression
        if (!check()) return Double.NaN;

        // 3. infix to postfix
        inToPost();

        // 4. calculate
        return calc();
    }

    private void trim() {
        int i, j;
        char[] cAry = content.toCharArray();

        for (i = 0; i < cAry.length; i++)
            if (Character.isWhitespace(cAry[i])) break;

        // if there is no whitespace in content
        if (i == cAry.length) return;

        // triming operation
        for (j = i + 1; j < cAry.length; j++)
            if (!Character.isWhitespace(cAry[j])) cAry[i++] = cAry[j];

        // Update content
        content = String.valueOf(cAry, 0, i);
    }

    private boolean check() {
        char[] cAry = content.toCharArray();

        if (cAry.length == 0) {
            System.out.println("Empty String!");
            return false;
        }

        // 1. check whether the first and last character is valid
        if (isOperator(cAry[0]) || cAry[0] == ')') {
            System.out.println("First character wrong!");
            return false;
        }

        if (isOperator(cAry[cAry.length - 1]) || cAry[cAry.length - 1] == '(') {
            System.out.println("Last character wrong!");
            return false;
        }

        // 2. check whether all characters are valid
        for (int i = 0; i < cAry.length; i++) {
            if (!(isDigit(cAry[i]) || isOperator(cAry[i]) || isBracket(cAry[i]))) {
                System.out.println("Invalid character: " + cAry[i]);
                return false;
            }
        }

        // 3. check whether operators are used properly
        for (int i = 0; i < cAry.length; i++) {
            char ch;

            if (isOperator(cAry[i])) {
                ch = cAry[i - 1];
                if (isOperator(ch) || ch == '(') return false;
                ch = cAry[i + 1];
                if (isOperator(ch) || ch == ')') return false;
            }
        }

        // 4. check whether parentheses are used properly
        int count = 0;
        for (int i = 0; i < cAry.length; i++) {
            if      (cAry[i] == '(') count++;
            else if (cAry[i] == ')') count--;

            if (count < 0) {
                System.out.println("Parentheses wrong!");
                return false;
            }
        }

        if (count != 0) {
            System.out.println("Parentheses wrong!");
            return false;
        }

        return true;
    }

    private void inToPost() {
        int debug_i = 0;
        char             temp;
        char[]           cAry   = content.toCharArray();
        Deque<Character> oStack = new ArrayDeque<>();

        for (int i = 0; i < cAry.length; i++) {
            if        (isDigit(cAry[i]))    {   // read a number
                int j = i;
                while (++j < cAry.length && isDigit(cAry[j]));
                postfix.push(new Token(Double.parseDouble(String.valueOf(cAry, i, j - i))));
                i = j - 1;
            } else if (isOperator(cAry[i])) {   // read a operator
                while (!oStack.isEmpty()) {
                    temp = oStack.peek();
                    if (rank(cAry[i]) > rank(temp)) {
                        break;
                    } else {
                        postfix.push(new Token(oStack.pop()));
                    }
                }
                oStack.push(cAry[i]);
            } else if (cAry[i] == '(')      {   // read a left bracket
                oStack.push('(');
            } else                          {   // read a right bracket
                while ((temp = oStack.pop()) != '(')
                    postfix.push(new Token(temp));
            }
        }

        while (!oStack.isEmpty())
            postfix.push(new Token(oStack.pop()));
    }

    private double calc() {
        Token           token;
        double          lhs, rhs, ret;
        Deque<Double>   nStack = new ArrayDeque<>();
        Iterator<Token> iter   = postfix.descendingIterator();

        while (iter.hasNext()) {
            token = iter.next();

            if (token.type == TYPE.DIGIT) {
                nStack.push(token.num);
            } else {
                rhs = nStack.pop();
                lhs = nStack.pop();

                switch (token.opt) {
                    case '+': ret = lhs + rhs; break;
                    case '-': ret = lhs - rhs; break;
                    case '*': ret = lhs * rhs; break;
                    case '/': ret = lhs / rhs; break;
                    case '^': ret = Math.pow(lhs, rhs); break;
                    default : ret = Double.NaN;
                }

                nStack.push(ret);
                // System.out.println(lhs + " " + token.opt + " " + rhs + " = " + ret);
            }
        }

        return nStack.pop();
    }

    private void printPostfix() {
        Token           token;
        Iterator<Token> iter = postfix.descendingIterator();

        while (iter.hasNext()) {
            token = iter.next();
            if (token.type == TYPE.DIGIT)
                System.out.print(token.num + " ");
            else
                System.out.print(token.opt + " ");
        }

        System.out.println();
    }

    /* Static Methods */
    private static boolean isDigit(char ch) {
        return Character.isDigit(ch) || ch == '.';
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*'|| ch == '/' || ch == '^';
    }

    private static boolean isBracket(char ch) {
        return ch == '(' || ch == ')';
    }

    private static int rank(char ch) {
        switch (ch) {
            case '^': return 3;
            case '*':
            case '/': return 2;
            case '+':
            case '-': return 1;
            default : return 0;
        }
    }

    /* Main Test */
    public static void main(String[] args) {
        Scanner    in         = new Scanner(System.in);
        Expression expression = new Expression();

        while (true) {
            // prompt
            System.out.println("Please enter your expression:");

            // read expression
            expression.setContent(in.next());

            // print result
            System.out.printf("= %.4f\n\n", expression.getValue());
        }
    }
}
